package datastructure.tree.bst2;


/**
 * 二叉搜索树-查找最大最小
 *
 * @author 杨 强
 * @package datastructure.tree.bst2
 * @createTime 2023-03-21 21:50
 */
public class BST02MinMax {
    public static void main(String[] args) {
        /*
                3
              2   4
            1
         */
        TreeNode node1 = new TreeNode(1, "1", null, null);
        TreeNode node2 = new TreeNode(2, "2", node1, null);
        TreeNode node4 = new TreeNode(4, "4", null, null);
        TreeNode node3 = new TreeNode(3, "3", node2, node4);
        BST02MinMax bst01 = new BST02MinMax(node3);
        System.out.println("预计1,实际:" + bst01.min());
        System.out.println("预计4,实际:" + bst01.max());
    }

    /**
     * 二叉搜索树的根节点
     */
    TreeNode root;

    public BST02MinMax(TreeNode root) {
        this.root = root;
    }

    /**
     * 查找最小-递归版
     * @return
     */
    public Object min() {
        return doMin(root);
    }
    public Object doMin(TreeNode node) {
        if (node == null) {
            return null;
        }
        // 左边已走到头
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }

    /**
     * 查找最小-非递归版
     * @return
     */
    public Object min1() {
        if (root == null) {
            return null;
        }
        TreeNode p = root;
        // 左边未走到头
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    /**
     * 查找最大-递归版本
     * @return
     */
    public Object max() {
        return doMax(root);
    }

    public Object doMax(TreeNode node) {
        if (node == null) {
            return null;
        }
        // 右边已走到头
        if (node.right == null) {
            return node.value;
        }
        return doMax(node.right);
    }


    /**
     * 查找最大-非递归版本
     * @return
     */
    public Object max1() {
        if (root == null) {
            return null;
        }
        TreeNode p = root;
        // 右边未走到头
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

}
